# 环形链表II: https://leetcode-cn.com/problems/linked-list-cycle-ii/


class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

# 这些都是错误的， 看最后一个
class Solution1:
    def detectCycle(self, head: ListNode) -> ListNode:
        """
            我的思路：杂糅了之前做的好几题
            1.先判断存在环 环形链表： https://leetcode-cn.com/problems/linked-list-cycle/
            2. （前面是快慢指针求得）， 只动快指针， 再次fast，low重合时，记录下环的长度。
            3. 问题就转变为了，求倒数第n个结点！ 删除链表的倒数第n个结点: https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
            时间复杂度都是n ，总体时间复杂度为 O(3n), 空间复杂度O(1)
        """
        low = head
        fast = head.next.next
        # 如果链表长度小于 1， 没有环
        if not head or not head.next:
            return None
        print(123)
        # 1. 
        while fast != low:
            # 当走到头了，没有环
            if not fast.next or not fast.next.next:
                return None
            fast = fast.next.next
            low = low.next
        print(123)
        # 2.
        n = 2
        fast = fast.next
        while fast.next != low:
            fast = fast.next
            n += 1 
        print(456)
        # 3. 找到倒数第n个节点
        fast = low = head
        for i in range(n - 1): fast = fast.next
        index = 0
        while fast.next:
            fast = fast.next
            low = low.next
            index += 1

        return index

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        """
            我的思路：杂糅了之前做的好几题
            这道题难在分析出公式，可以看解析，如何求出来
        """
        low = head
        fast = head.next.next
        # 如果链表长度小于 1， 没有环
        if not head or not head.next:
            return None
        print(123)
        # 1. 判断是否有环
        while fast != low:
            # 当走到头了，没有环
            if not fast.next or not fast.next.next:
                return None
            fast = fast.next.next
            low = low.next
        print(fast is low)
        # 2. 找到环开始下标
        n = 0
        p = head
        while fast != p:
            fast = fast.next
            p = p.next
            n += 1 
        return n

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        """
            我的思路：杂糅了之前做的好几题
            这道题难在分析出公式，可以看解析，如何求出来
        """
        # 如果链表长度小于 1， 没有环
        if not head or not head.next:
            return None
        low = head.next
        fast = head.next.next
        print(123)
        # 1. 判断是否有环
        while fast != low:
            # 当走到头了，没有环
            if not fast.next or not fast.next.next:
                return None
            fast = fast.next.next
            low = low.next
        print(fast.val, low.val)
        # 2. 找到环开始下标
        p = head
        while fast != p:
            fast = fast.next
            p = p.next
        
        print(p.val, fast.val)
        return p.val




# 正确的解题思路：
class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        """
            我的思路：杂糅了之前做的好几题
            这道题难在分析出公式，可以看解析，如何求出来. 不管公式中 n 为何值， 他们一定在循环开始出相遇。
        """
        # 如果链表长度小于 1， 没有环
        if not head or not head.next:
            return None
        fast = low = head
        # 1. 判断是否有环
        while fast.next and fast.next.next:
            # 当走到头了，没有环
            fast = fast.next.next
            low = low.next
            # 1. 找到环了
            if fast == low:
                p = head
                while fast != p:
                    fast = fast.next
                    p = p.next
                return p

        # 2. 没找到环        
        return None

a = ListNode(2)
b = ListNode(0)
c = ListNode(-4)
head = ListNode(3)
head.next = a
a.next = b
b.next = c
c.next = a

s = Solution()
rst = s.detectCycle(head)
print(rst)

